package com.lss.d_substr;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author lss
 * @description
 * @createDate 2024/12/4-16:22
 */
public class lc_239 {
    public static void main(String[] args) {

    }

    /**
     * 返回获得每一个滑动窗口中的最大值
     * 超出时间限制
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        for (int i = k - 1; i < nums.length; i++) {
            int max = nums[i];
            for (int j = i - k + 1; j < i; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
            ans[i - k + 1] = max;
        }

        return ans;
    }

    public int[] maxSlidingWindowByMe(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // 数据校验
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {
                deque.removeLast();
            }

            // 数据添加
            deque.addLast(i);

            // 控制范围
            if (i - deque.getFirst() >= k) {
                deque.removeFirst();
            }
            // 添加元素
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[deque.getFirst()];
            }

        }
        return ans;
    }

    /**
     * 000000000000000000
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow_0(int[] nums, int k) {
        int[] ans = new int[nums.length - k + 1];//初始化ans
        //使用双向队列存储元素
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // 元素修正
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {
                deque.removeLast();
            }
            //
            deque.addLast(i);
            //移除越界元素
            if ((i - deque.getFirst()) >= k) {
                deque.removeFirst();
            }
            //添加元素
            if (i >= k - 1) {
                ans[i - k + 1] = nums[deque.getFirst()];
            }

        }
        return ans;
    }
}
